package huffmanmsn;


import Heap.VectorHeap;
import HuffmanTrees.BinaryTree;
import HuffmanTrees.HuffmanTree;
import HuffmanTrees.Node;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Vector;


/**
 * Take a string and encode it with the huffman codification.
 * @author Vinicio Gomez
 * @since 13/09/2012
 * @version 1.0
 */
public class HuffmanMsn {
    static ArrayList<Node> codigos = new ArrayList<Node>();
    /**
     * Driver del programa.
     * @param args the command line arguments
     * @throws IOException  si el ingreso de teclado no es valido
     */
    public static void main(String[] args) throws IOException {
        System.out.println("Hoja de Trabajo #6: Algoritmo de Huffman");
        System.out.println("Autor: Vinicio Gomez (viniciomvp@hotmail.com)");
        System.out.println();
        System.out.println("Ingrese una cadena de caracteres."
                + " Luego presione Enter.");
        //arreglo de nodos con caracteres y frecuencias
        ArrayList<Node> freq = new ArrayList<Node>();
        //ingreso de cadena
        String s;
        s = new Scanner(System.in).nextLine();
        
        //se separa por caracteres la cadena
       for (int x=0; x< s.length(); x++)
        {   char c = s.charAt(x);
            if (c == '\n') {
                continue;
            }
            //Se busca la frecuencia de cada caracter
            boolean sumo=false;
            for (Node query: freq){
                //si el caracter existe se aumenta en uno la frecuencia.
                if (query.getCh() == c){
                    freq.get(freq.indexOf(query)).addFreq();
                    sumo=true;
                    break;
                }
            }
            //si el caracter no existe se agrega a la lista de caracteres
            if (!sumo){
                freq.add(new Node(c));  
            }
            sumo=false;
        }
       
        //Se crean Arboles de Huffman para cada caracter y su frecuencia
        ArrayList<HuffmanTree> array_elements = new ArrayList<HuffmanTree>();
        for (Node elemento: freq){            
            array_elements.add(new HuffmanTree(elemento));
        }
        
        //Los datos son trasladados a de un ArrayList a un Vector
        Vector datos = new Vector(array_elements);
        //Se inicializa el Heap con los datos del vector
        VectorHeap<HuffmanTree> trees = new VectorHeap<HuffmanTree>(datos);
        
        // Se combinan los Arboles hasta que solo quede uno.
        while (trees.size() > 1)
        {
            // Se toman los menores con la ayuda del Heap
            HuffmanTree smallest = trees.remove();
            HuffmanTree small = trees.remove();
            // Se unen y el resultado se agrega al vector
            trees.add(new HuffmanTree(smallest,small));
        }
        //----------------------------------------------
        //----------------------------------------------
        //Impresion de resultados
        ArrayList<Node> codigos=null;
        System.out.println();
        System.out.println("caracter - frecuencia - codigo Huffman");
        if (trees.size()==1){//si la cadena no esta vacia
            //se obtiene el primer arbol y se envia    
            codigos = recursivo (trees.getFirst().getRoot(),"*");
        }
        //----------------------------------------------------------------------
        //de codigo a caracteres
        System.out.println();
        System.out.println("Ingrese una cadena valida de codigo Huffman segun"
                + " la codificacion mostrada anteriormente.");
        //ingreso de datos
        s = new Scanner(System.in).nextLine();
        
        System.out.println();
        System.out.print("El mensaje decodificado es: ");
        
        int inicio =0;
        int fin = 1;
        while (fin != s.length()+1){    
            //se va recorriendo el ingreso 
            String code = s.substring(inicio,fin);
            //System.out.println(code);
            for (Node n: codigos){
                //System.out.print(n.getCh() +" "+ n.getRepr());
                if (n.getRepr().equals(code)){
                    System.out.print(n.getCh());
                    inicio=fin;
                }   
            }
            fin++;
        }
        System.out.println();
        System.out.println();
        System.out.println("Autor: Vinicio Gomez  viniciomvp@hotmail.com");
    }

    /**
     * Nos permite viajar en el Arbol final de Huffman y codificar los 
     * caracteres.
     * @param origen Arbol raiz.
     * @param codigo Codigo recopilado segun el recorrido.
     * @return Un arrayList de los nodos con los codigos.
     * @since 14/09/2012
     */
    private static ArrayList<Node> recursivo(BinaryTree origen,String codigo) {
            
            //Se verifica lado izquierdo del arbol
            if (!origen.isLeft()){
                recursivo (origen.left(),codigo.concat("0"));
            }
            //Se verifica lado derecho del arbol
            if (!origen.isRight()){
                recursivo (origen.right(),codigo.concat("1"));
            }
            //Se opera el nodo actual
            Node nuevo = (Node)origen.value();
            try{
                //Si el caracter es "-" no es el final del arbol y no se imprime
                if (nuevo.getCh()!='-'){

                    
                    char[] codigo2= new char[codigo.length()-1];
                    for (int x = 1; x<codigo.length(); x++){
                        codigo2[x-1]=codigo.charAt(x);    
                    }
                    nuevo.setRepr(String.valueOf(codigo2)); //asignacion de los codigos
                    codigos.add(nuevo);
                    //comentar esta linea si unicamente se desea asignar codigos
                    System.out.println(String.valueOf(nuevo.getCh())+"        "
                            + "  "+ nuevo.getFreq()+"           "+nuevo.getRepr());
                }
            }
            catch (Exception e){
                
            } 
            return codigos;
    }

    
}
